package com.heima.leetcode.practice;

/**
 * leetcode 96. 不同的二叉搜索树，卡特兰数，和这个一模一样的代码是出栈序列
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/12 11:37
 */
public class E96 {
    /*
      卡特兰数：
      C0 = 1， C1 = 1， C2 = 2， C3 = 5， C4 = 14， C5 = 42， C6 = 132， C7 = 429， C8 = 1430， C9 = 4862， C10 = 16796， C11 = 58786， C12 = 208012， C13 = 742900，C14 = 2674440， C15 = 9694845，

      此问题n=1时 有1种，n=2时 有2种，n=3时 有5种，n=4时 有14种 ...

      可见此问题的求解numTrees(n) == C(n)
     */

    /**
     * <h3>方法一：用卡特兰数进行求解配合动态规划</h3>
     *
     * @param n 整数n
     * @return 有多少种不同的二叉搜索树
     */
    public int numTrees(int n) {
        // 1. 创建dp数组
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 1-i每次选一个作为根节点，剩下的放到两边，统计数量
            for (int j = 1; j <= i; j++) {
                // 拆分为子问题，选一个过后，左子树有j-1个节点，右子树有i-j个节点，分别统计子树的数量
                dp[i] += dp[j - 1] * dp[i - j]; // 左子树的种类乘以右子树的种类
            }
        }
        return dp[n];
    }

    private int[] memory; // 记忆数组

    /**
     * <h3>方法二：递归配合记忆法</h3>
     *
     * @param n 整数n
     * @return 有多少种不同的二叉搜索树
     */
    public int numTrees2(int n) {
        memory = new int[n + 1];
        memory[0] = 1;
        memory[1] = 1;
        return numsTrees(n);
    }

    /**
     * 递归
     * @param n 整数n
     * @return 有多少种不同的二叉搜索树
     */
    private int numsTrees(int n){
        // 1. n 为1或0，直接返回
        if (n == 1 || n == 0){
            return memory[n];
        }
        // 2. 递归计算
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (memory[i - 1] == 0) {
                memory[i - 1] = numsTrees(i - 1);
            }
            if (memory[n - i] == 0){
                memory[n - i] = numsTrees(n - i);
            }
            result += memory[i - 1] * memory[n - i];
        }
        return result;
    }
}
